package com.cb2.algorithm.leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;

/**
 * <a href="https://leetcode.cn/problems/linked-list-random-node/">链表随机节点</a>
 * <p>给你一个单链表，随机选择链表的一个节点，并返回相应的节点值。每个节点 被选中的概率一样 。</p>
 * <p>
 * 实现 Solution 类：
 * <li>Solution(ListNode head) 使用整数数组初始化对象。</li>
 * <li>int getRandom() 从链表中随机选择一个节点并返回该节点的值。链表中所有节点被选中的概率相等。</li>
 * <pre>
 * 示例：
 *      输入
 *          ["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]
 *          [[[1, 2, 3]], [], [], [], [], []]
 *      输出
 *          [null, 1, 3, 2, 2, 3]
 *      解释
 *          Solution solution = new Solution([1, 2, 3]);
 *          solution.getRandom(); // 返回 1
 *          solution.getRandom(); // 返回 3
 *          solution.getRandom(); // 返回 2
 *          solution.getRandom(); // 返回 2
 *          solution.getRandom(); // 返回 3
 *          // getRandom() 方法应随机返回 1、2、3中的一个，每个元素被返回的概率相等。
 * </pre>
 * <b>提示：</b>
 * <li>链表中的节点数在范围 [1, 10^4] 内</li>
 * <li>-10^4 <= Node.val <= 10^4</li>
 * <li>至多调用 getRandom 方法 10^4 次</li>
 *
 * <b>进阶：</b>
 * <li>如果链表非常大且长度未知，该怎么处理？</li>
 * <li>你能否在不使用额外空间的情况下解决此问题？</li>
 *
 * @author c2b
 * @since 2023/5/4 17:20
 */
public class LC0382LinkedListRandomNode_M {
    static class Solution {
        private final Random random;
        private final List<Integer> list;

        public Solution(ListNode head) {
            random = new Random();
            list = new ArrayList<>();
            while (head != null) {
                list.add(head.val);
                head = head.next;
            }
        }

        public int getRandom() {
            return list.get(random.nextInt(list.size()));
        }
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        Solution solution = new Solution(head);
        Map<Integer, Integer> cntMap = new HashMap<>();
        final int TIMES = 1000000000;
        for (int i = 0; i < TIMES; i++) {
            int random = solution.getRandom();
            cntMap.put(random, cntMap.getOrDefault(random, 0) + 1);
        }
        for (Map.Entry<Integer, Integer> entry : cntMap.entrySet()) {
            System.out.println("数字[" + entry.getKey() + "]出现的频次为：[" + entry.getValue() + "]，概率为：" + entry.getValue() * 1.0 / TIMES);
        }
    }
}